# 要用递推矩阵的最关键的一步就是先找到递推公式，在转换成递推矩阵，可惜，我不会。
# 咱们照例百度一下：那么，没有找到，额，那只能抄之前的c语言代码了
def multiply(A, B, mod):
    x = [i for i in range(A.x)]
    C = matrix(A.x)
    for i in x:
        for j in x:
            C.a[i][j] = 0
            for k in x:
                C.a[i][j] += A.a[i][k] * B.a[k][j] % mod
                C.a[i][j] %= mod
    return C
    
class matrix:
    
    def __init__(self, x, a = []): # x是阶数
        self.x = x
        self.rx = [i for i in range(x)]
        self.a = [[0] * x for i in self.rx]
        if a != []: self.a = a

    def copy(self):
        tmp = matrix(self.x)
        for i in self.rx:
            for j in self.rx:
                tmp.a[i][j] = self.a[i][j]
        return tmp
        
    def unit(self):
        try:
            return matrix(self.x, self.u)
        except:
            self.u = [[0] * self.x for i in self.rx]
            for i in range(self.x):
                for j in range(self.x):
                    if i == j: self.u[i][j] = 1
            return matrix(self.x, self.u)

    def pow(self, n, mod):
        res = self.unit()
        temp = self
        while n:
            if n & 1: res = multiply(res, temp, mod)
            temp = multiply(temp, temp, mod)
            n >>= 1
        return res
    
def fib(n, mod):
    res, A = matrix(2), matrix(2)
    res.a[0][0], res.a[0][1], res.a[1][0], res.a[1][1] = 1, 1, 1, 0
    A = res.copy()
    A.a[0][1] = 0
    res = res.pow(n - 1, mod)
    return multiply(res, A, mod).a[1][0]

n, m = map(int, input().split())
print(fib(n, m))
'''

上述的res矩阵和A矩阵如下：

      | 1 1 |      | 1 0 |
res = | 1 0 |, A = | 1 0 |, 其中A的上边是f[2], A的下边是f[1]

              | 2 0 |
已知res * A = | 1 0 |, 其中上边是f[3], 下边是f[2]

                           | 3 0 |
再乘1次，res * (res * A) = | 2 0 |, 其中上边是f[4], 下边是f[3]

也就是说，根据res的特性，他可以帮我们递推出结果，也就是n-2个res相乘再乘A，取a[0][0]

或者像我上面写的，n-1个res相乘再乘A，取a[1][0]。

因为n是从1到1e18的，所以为了不出现负数，我们不使用n-2个相乘的方法，而是用n-1个相乘的方法。

然后再结合快速幂，我们可以以O(2^3 * lgn)的时间复杂度解决问题。

'''
'''

from random import randint as r
nn = [(1, 100), (500, 20000), (50000000, 200000000), (int(5e13), int(2e14)), (int(9e17), int(1e18))]
mm = [(1, 100), (500, 2000), (50000, 200000), (int(5e6), int(2e7)), (int(9e7), int(1e8))]
for ww in range(len(nn)):
    n, m = r(*nn[ww]), r(*mm[ww])
    s_i = f"{n} {m}\n"
    print(n, m, fib(n, m))
    s_o = f"{fib(n, m)}"
    with open(f"{ww + 1}.in", 'w') as f:
        f.write(s_i)
    with open(f"{ww + 1}.out", 'w') as f:
        f.write(s_o)
'''
# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。
